/**
 * 用栈实现队列
 */
#include <iostream>
#include <stdexcept>

using namespace std;

// 栈内元素定制化，模板实现
template <typename T>
class Stack
{
private:
    T *data;       // T类型的数组
    int size;      // 元素个数
    int capacity;  // 容量
    void resize(); // 扩容函数

public:
    Stack() : data(new T[10]), size(0), capacity(10) {}
    ~Stack();

    // 入
    void push(T element);
    // 出
    T pop();
    // 获取栈顶元素
    T top() const;
    // 获取元素个数
    int getSize() const;
    // 是否为空
    bool empty();
};

template <typename T>
void Stack<T>::resize()
{
    int nNewCapacity = capacity * 2;
    T *newData = new T[nNewCapacity];
    for (int i = 0; i < size; ++i)
    {
        newData[i] = data[i];
    }
    delete[] data;
    data = newData;
    capacity = nNewCapacity;
}

template <typename T>
Stack<T>::~Stack()
{
    delete[] data;
}

template <typename T>
void Stack<T>::push(T element)
{
    if (size == capacity)
    {
        resize();
    }
    data[size++] = element;
}

template <typename T>
T Stack<T>::pop()
{
    if (size == 0)
    {
        throw std::underflow_error("Stack is empty");
    }
    return data[--size];
}

template <typename T>
T Stack<T>::top() const
{
    if (size == 0)
    {
        throw std::underflow_error("Stack is empty");
    }
    return data[size - 1];
}

template <typename T>
int Stack<T>::getSize() const
{
    return size;
}

template<typename T>
bool Stack<T>::empty()
{
    return size == 0;
}

// 队列
class MyQueue
{
private:
    Stack<int> s1;   // 主栈
    Stack<int> s2;   // 副栈
public:
    MyQueue(/* args */);
    ~MyQueue();
    // 入队
    void push(int x) 
    {   
        s1.push(x);
    }
    // 出队
    int pop()
    {
        if (s2.empty())
        {
            while (!s1.empty())
            {
                s2.push(s1.pop());
            }
        }
        return s2.pop();    // 弹出s2的栈顶元素
    }
    // 获取栈顶元素
    int peek()
    {
        if (s2.empty())
        {
            while (!s1.empty())
            {
                s2.push(s1.pop());
            }
        }
        return s2.top();
    }
    // 判空
    bool empty()
    {
        return s1.empty() && s2.empty();
    }
};

MyQueue::MyQueue(/* args */)
{
}

MyQueue::~MyQueue()
{
}
